package code1.binary_tree;

import java.util.*;

/**
 * 前序、后序、中序遍历(迭代法)
 * 原题链接：
 * https://leetcode.cn/problems/binary-tree-preorder-traversal/
 * https://leetcode.cn/problems/binary-tree-postorder-traversal/
 * https://leetcode.cn/problems/binary-tree-inorder-traversal/
 */
public class P144_2 {

    //前序遍历(迭代)
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        if(root==null){
            return result;
        }
        stack.add(root);
        while (!stack.isEmpty()){
            TreeNode top = stack.pop();         //根
            result.add(top.val);
            if(top.right!=null){
                stack.push(top.right);              //右(先右后左，出栈顺序为先左后右)
            }
            if(top.left!=null){
                stack.push(top.left);               //左
            }
        }
        return result;
    }

    //中序遍历(迭代)
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        if(root==null){
            return result;
        }
        TreeNode cur=root;      //当前节点
        while(!stack.isEmpty() || cur!=null){
            if(cur!=null){          //一直左到底
                stack.push(cur);
                cur=cur.left;           //左
            }else{
                cur=stack.pop();
                result.add(cur.val);    //中
                cur=cur.right;          //右
            }
        }
        return result;
    }

    //后序遍历(迭代)
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        if(root==null){
            return result;
        }
        stack.add(root);
        while (!stack.isEmpty()){
            TreeNode top = stack.pop();         //根
            result.add(top.val);
            if(top.left!=null){
                stack.push(top.left);               //左
            }
            if(top.right!=null){
                stack.push(top.right);              //右
            }
        }
        Collections.reverse(result);
        return result;
    }

}
